//按摩师
class Solution {
public:
    int massage(vector<int>& nums) {
        //f(x)的状态表示：到x位置时，若我选该位置的值的最大预约时长
        //g(x)的状态表示：到x位置时，若我不选该位置的值的最大预约时长
        //f(x)状态转移方程：f(x) = g(x-1)+nums(x);
        //若x位置不选，则前一个位置可以选，g(x) = f(x-1)
        //若x位置不选，则前一个位置也可以不选，g(x) = g(x-1)
        //g(x)状态转移方程: g(x) = max(g(x-1),f(x-1))
        size_t n = nums.size();

        vector<int> f(n);
        vector<int> g(n);
        if(n == 0)
        {
            return 0;
        }
        f[0] = nums[0];
        for(size_t i = 1 ; i < n ; ++i)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(g[i-1],f[i-1]);
        }
         return max(f[n-1],g[n-1]);
    }
};

//打家劫舍II
class Solution {
public:
    int _rob(vector<int>& nums,int begin,int end)
    {
        //2 3 1
        std::cout <<"Debug"<<std::endl;
        if(begin > end)
            return 0;
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        f[begin] = nums[begin];

        for(size_t i = begin+1 ; i <= end ; ++i)
        {
            f[i] = g[i-1]+nums[i];
            g[i] = max(f[i-1],g[i-1]);
        }
        return max(f[end],g[end]);
    }
    int rob(vector<int>& nums) {
        //f(x)状态表示：以x位置为结尾，若选这个位置的值后的最大值
        //g(x)状态标识：以x位置为结尾，若不选这个位置的值后的最大值
        //f(x) = g(x-1)+nums(x);
        //g(x) = max(f(x-1),g(x-1))
        if(nums.size() == 1)
        {
            return nums[0];
        }
        int rob_begin = _rob(nums,2,nums.size()-2)+nums[0];
        int rob_end = _rob(nums,1,nums.size()-1);
        return max(rob_begin,rob_end);
    }
};

//删除并获得点数
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = 10001;
        vector<int> arr(n);
        int size = INT_MIN;
        for(auto& e : nums)
        {
            if(e > size) size = e;
            arr[e] += e;
        }

        vector<int> f(size+1);
        vector<int> g(size+1);
        for(size_t x = 1 ; x <= size ; ++x)
        {
            f[x] = g[x-1] + arr[x];
            g[x] = max(g[x-1],f[x-1]);
        }
        return max(f[size],g[size]);
    }
};

